[Day14] 初見碰撞系統

13th鐵人賽 c opengl 遊戲製作電腦圖學

POKA

2021-09-24 23:49:01

1213 瀏覽

分享至

到目前為止，我們有了時間，可以輸入，還可以對「物件」進行位移，看來可以開始讓「小鐵(LittleIron)」開始跑跑跳跳了，就像那名傳奇的水管工一樣，但在這之前我想先讓小鐵「腳踏實地」，這個就會需要一些基本的碰撞知識了。

今日目標

初步了解幾個常見的碰撞演算法
AABB碰撞偵測演算法

碰撞偵測與解析與這款遊戲

物理引擎與遊戲中，所說到的碰撞，整個流程應該拆成兩種，偵測與碰撞。

偵測就是回答兩個物體有沒有接觸或撞在一起的方法；解析則是碰撞之後，對於這些「碰撞到的點要做甚麼」的處理方法。由於目標是2D遊戲，一定比3D處理簡單N倍，而且事實上也不會套入真正的物理處理(各式各樣的「力」)，又更加簡單了。

注意: 簡單不代表容易 (Simple does not mean easy to do...)

最重要的還有一點，我們遊戲物件的碰撞「框」，預測大部分都會是都會是矩形，而且是不會旋轉的，這又大大減少難度，原因是有這麼多碰撞偵測的演算法，都是考慮這些圖形或模型是不規則(凸體(Convex))，且可能會進行位移旋轉之類操作的。

所以接下來，做個實驗看看，來看看就簡單的碰撞偵測演算法 - AABB。

實驗: AABB

AABB是Axis-Aligned Bounding Box的簡稱，從名字就可以看出來Bounding Box，會是把我們要檢測的物件用一個Box裝起來，不論是否旋轉或是是不規則的形狀，然後互相比對各軸的最大與最小的邊界，然後就可以決定是不是碰撞了，簡單標示一下，其實就可以看得懂了:

//         x1 min       x1 max
//    y1 max +------------+
//           |            |
//           |        +---|--------+ y2 max
//           |        |   |        |
//           |        |   |        |
//    y1 min +--------|---+        |
//                    |            |
//                    +------------+ y2 min
//                   x2 min      x2 max

if (x2 min > x1 max && x1 min < x2 max
   && y1 min < y2 max %&& y2 min < y1 max) 
   {
       // Collision!!
   }

其實核心就是這樣子，如上面所說的比較各軸可以知道答案了。下面直接貼上我測試的code，可以參考看看

// struct for our game object
    typedef struct {
        V2f pos;
        V2f speed;
        V2f size;
        Color c;
    } Entity;


// in `Game Loop`
       float dt = GetDeltaTime();
        if (IsKeyDown(KEY_RIGHT)) {
            p.pos.x += p.speed.x * dt;
        } else if (IsKeyDown(KEY_LEFT)) {
            p.pos.x -= p.speed.x * dt;
        }

        if (IsKeyDown(KEY_DOWN)) {
            p.pos.y += p.speed.y * dt;
        } else if (IsKeyDown(KEY_UP)) {
            p.pos.y -= p.speed.y * dt;
        }

        // AABB
        float box_x_min = box.pos.x - box.size.x / 2.0f;
        float box_x_max = box.pos.x + box.size.x / 2.0f;
        float box_y_min = box.pos.y - box.size.y / 2.0f;
        float box_y_max = box.pos.y + box.size.y / 2.0f;

        float p_x_min = p.pos.x - p.size.x / 2.0f;
        float p_x_max = p.pos.x + p.size.x / 2.0f;
        float p_y_min = p.pos.y - p.size.y / 2.0f;
        float p_y_max = p.pos.y + p.size.y / 2.0f;

        if (p_x_max >= box_x_min && p_x_min <= box_x_max
            && p_y_max >= box_y_min && p_y_min <= box_y_max) {
            p.c = COLOR_PURPLE;
            box.c = COLOR_ORANGE;
        } else {
            p.c = COLOR_WHITE;
            box.c = COLOR_WHITE;
        }

功能是，如果碰撞就變換顏色，但以我們遊戲來講，應該是要阻擋兩個物件可以重疊才對。

其他我還「聽過」的演算法

其實之前就聽過一些碰撞偵測的演算法了，但也都是聽過。因為數學的關係，讓我卻步，於是趁這機會多接觸一下，以下是我對這些演算法的初步了解(胡言亂語)。

SAT: 分離軸碰撞檢測(Separating Axis Theorem)，印象中這個做法是利用凸體頂點在某個軸(這個軸怎麼來的)的投影，利用投影檢測是否重疊表示碰撞。
GJK: 完全不知道，只知道這是以三的人的名字命名的(Gilbert–Johnson–Keerthi) (ˊ_>ˋ)
EPA: 完全不知道這是甚麼，好像是要搭配GJK完成的演算法 (ˊ_>ˋ)